package com.zklh.leetcode.top100.problem23;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 合并k个链表算法实现
 * @author 坐看落花
 * @version 1.0
 * @date 2021/11/7 13:50
 */
public class Solution23 {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (ListNode node : lists) {
            if (node != null) {
                queue.add(node);
            }
        }
        ListNode head = new ListNode();
        ListNode last = head;
        while (!queue.isEmpty()) {
            last.next = queue.poll();
            last = last.next;
            if (last.next != null) {
                queue.add(last.next);
            }
        }
        return head.next;
    }



    private static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void main(String[] args) {
        ListNode[] listNodes = new ListNode[0];


        Solution23 solution23 = new Solution23();
        ListNode node = solution23.mergeKLists(listNodes);
        while (node != null) {
            System.out.print(node.val+",");
            node = node.next;
        }
    }
}
